package com.LeetCode.DFS;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 查找所有递增子序列
 */
public class FindSubsequences {

    List<Integer> tmp = new ArrayList<>();
    List<Integer> res = new ArrayList<>();

    public List<Integer> findSubsequences(int[] nums) {
        dfs(0, Integer.MIN_VALUE, nums);
        return res;
    }

    public int[] LIS (int[] arr) {
        dfs(0, Integer.MIN_VALUE, arr);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    public void dfs(int index, int last, int[] nums){
        if(index == nums.length){
            if(tmp.size() > res.size()) {
                res = new ArrayList<>(tmp);
            }else if (tmp.size() == res.size()){
                int k = 0;
                for(int i = 0; i<tmp.size(); i++){
                    if(!tmp.get(i).equals(res.get(i))){
                        k = i;
                        break;
                    }
                }
                if(tmp.get(k) < res.get(k))
                    res = new ArrayList<>(tmp);
            }
            return;
        }

        if(nums[index] >= last){
            tmp.add(nums[index]);
            dfs(index + 1, nums[index] , nums);
            tmp.remove(tmp.size() - 1);
        }

        if(nums[index] != last){
            dfs(index + 1, last, nums);
        }
    }

    @Test
    public void test(){
        int[] arr = {1,2,8,6,4};
        for(int num : LIS(arr)){
            System.out.print(num + " ");
        }
    }

}
